public class Day5 {

    public static void main(String[] args) {
        int[] arr = {2,5,3,7,101,18};
    }

    //最长递增子序列

    //记忆化搜索
    int n ;
    int[] memo;//以某个数开始的最长子序列长度
    public int lengthOfLIS(int[] nums) {
        n = nums.length;
        memo = new int[n];//保存
        int len=0;
        for(int i=0;i<n;i++) {
            len = Math.max(dfs(i,nums),len);
            //memo[i]=len;
        }
        return len;
    }
    public int dfs(int pos,int[] nums) {
        if(memo[pos]!=0) return memo[pos];
        int len=1;
        for(int i=pos+1;i<n;i++) {
            if(nums[i]>nums[pos])
                len = Math.max(len,dfs(i,nums)+1);
        }
        memo[pos]=len;
        return len;
    }
    //动态规划
    public int lengthOfLISs(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for(int i=0;i<n;i++) {
            dp[i]=1;
        }
        int ret = 1;//记录返回值
        for(int i=1;i<n;i++) {
            //判断i位置的值可以跟在哪个值后面
            for(int j=i-1;j>=0;j--) {
                if(nums[i] > nums[j]) {
                    dp[i]=Math.max(dp[i],dp[j]+1);//跟的某个值后面是否为最大值
                }
            }
            ret = Math.max(ret,dp[i]);//取某个位置为结尾的最大值
        }
        return ret;
    }


}
